package com.example.javamaday.leetcode;

import com.example.javamaday.leetcode.base.ListNode;

public class LeetCodeTest0148 {

    public static void main(String[] args) {

    }


    public ListNode sortList(ListNode head) {
        if (head == null || head.next == null) {
            return head;
        }
        ListNode slow = head;
        ListNode fast = head;
        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
        }
        ListNode last = slow.next;
        slow.next = null;
        ListNode first = sortList(head);
        ListNode second = sortList(last);
        return merge(first, second);
    }

    private ListNode merge(ListNode first, ListNode second) {
        ListNode dumpy = new ListNode(Integer.MIN_VALUE);
        ListNode tail = dumpy;
        while (first != null && second != null) {
            if (first.val < second.val) {
                tail.next = first;
                first = first.next;
            } else {
                tail.next = second;
                second = second.next;
            }
            tail = tail.next;
        }
        tail.next = (first == null ? second : first);
        return dumpy.next;
    }
}
